package com.zbxx.leetcode.unionfind;


/**
 * 959 由斜杠划分区域
 *
 * @author wanrj
 * @date 2023/6/5
 */
public class regionsBySlashes {

    public int regionsBySlashes(String[] grid) {
        UnionFind unionFind = new UnionFind(grid.length);
        char[][] chars = new char[grid.length][grid.length];
        for (int i = 0; i < grid.length; i++) {
            chars[i] = grid[i].toCharArray();
        }
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars[i].length; j++) {
                unionSelf(i, j, chars, unionFind);
                unionRegionNeighbor(i, j, unionFind, chars.length);
            }
        }
        return unionFind.unique;
    }


    public static void unionSelf(int x, int y, char[][] grid, UnionFind find) {
        char s = grid[x][y];
        int index = getIndex(x, y, grid.length);
        if (s == '/') {
            find.union(index, index + 1);
            find.union(index + 2, index + 3);
        }
        if (s == '\\') {
            find.union(index, index + 3);
            find.union(index + 1, index + 2);
        }
        if (s == ' ') {
            find.union(index, index + 1);
            find.union(index, index + 2);
            find.union(index, index + 3);
        }
    }

    public static void unionRegionNeighbor(int x, int y, UnionFind find, int length) {
        int yr = y + 1;
        if (yr < length) {
            find.union(getIndex(x, y, length) + 2, getIndex(x, yr, length));

        }
        int xd = x + 1;
        if (xd < length) {
            find.union(getIndex(x, y, length) + 3, getIndex(xd, y, length) + 1);
        }
    }

    public static int getIndex(int x, int y, int length) {
        return x * length * 4 + y * 4;
    }


    public class UnionFind {

        private int parent[];

        int unique;


        public UnionFind(int size) {
            this.unique = size * size * 4;
            this.parent = new int[unique];
            for (int i = 0; i < this.parent.length; i++) {
                parent[i] = i;
            }
        }


        public void union(int x, int y) {
            int xr = find(x);
            int yr = find(y);
            if (xr == yr) {
                return;
            }
            unique--;
            parent[xr] = yr;
        }


        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

    }


    public static void main(String[] args) {
        regionsBySlashes r = new regionsBySlashes();
        System.out.println(r.regionsBySlashes(new String[]{"/\\", "\\/"}));
    }


}
